package binary_tree


func IsFull(root *Node) bool {
	if root == nil {return true}
	height := h(root)
	nodes := n(root)
	return (1<<height)-1 == nodes
}

func h(node *Node) int {
	if node == nil {
		return 0
	}
	return max(h(node.Left), h(node.Right))+1
}

func n(node *Node) int {
	if node == nil {
		return 0
	}
	return n(node.Left) + n(node.Right)+1
}

func IsFull2(root *Node) bool {
	if root == nil {
		return true
	}
	info := process_f(root)
	return (1<<info.height)-1 == info.nodes
}

type fInfo struct{
	height int
	nodes  int
}

func process_f(node *Node) fInfo {
	if node == nil {
		return fInfo{0,0}
	}
	linfo := process_f(node.Left)
	rinfo := process_f(node.Right)
	height := max(linfo.height, rinfo.height)+1
	nodes := linfo.nodes + rinfo.nodes + 1
	return fInfo{height,nodes}
}